|
In mathematics, a simple subcubic graph is a finite simple graph in which each vertex has degree at most three. Suppose we have a sequence of simple subcubic graphs ''G''1, ''G''2, ... such that each graph ''G''''i'' has at most ''i'' + ''k'' vertices (for some integer ''k'') and for no ''i'' < ''j'' is ''G''''i'' homeomorphically embeddable into (i.e. is a graph minor of) ''G''''j''. The Robertson–Seymour theorem proves that subcubic graphs (simple or not) are well-founded by homeomorphic embeddability, implying such a sequence cannot be infinite. So, for each value of ''k'', there is a sequence with maximal length. The function SSCG(''k'')〔http://www.cs.nyu.edu/pipermail/fom/2006-April/010305.html〕 denotes that length for simple subcubic graphs. The function SCG(''k'')〔http://www.cs.nyu.edu/pipermail/fom/2006-April/010362.html〕 denotes that length for (general) subcubic graphs. The ''SSCG'' sequence begins SSCG(0) = 2, SSCG(1) = 5, but then grows rapidly. SSCG(2) = 3 × 23 × 295 − 9 ≈ 103.5775 × 1028. SSCG(3) is not only larger than TREE(3), it is much, much larger than TREE(TREE(…TREE(3)…))〔https://cp4space.wordpress.com/2013/01/13/graph-minors/〕 where the total nesting depth of the formula is TREE(3) levels of the TREE function . Adam Goucher claims there’s no qualitative difference between the asymptotic growth rates of SSCG and SCG. He writes "It’s clear that SCG(''n'') ≥ SSCG(''n''), but I can also prove SSCG(4''n'' + 3) ≥ SCG(''n'')."〔https://cp4space.wordpress.com/2012/12/19/fast-growing-2/comment-page-1/#comment-1036〕 == See also == *Goodstein's theorem *Paris–Harrington theorem *Kanamori–McAloon theorem *Kruskal's tree theorem *Robertson–Seymour theorem 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Friedman’s SSCG function」の詳細全文を読む スポンサード リンク
|